package Year22_Month06.day17;

public class 平衡二叉树_迭代写法 {
    public boolean isBalanced(TreeNode root) {
        //用-1来判断是否高度差是否大于1
        return solve(root) != -1;
    }

    public int solve(TreeNode root){
        if(root == null) return 0;
        //拿到左子树的高度值，如果为-1就证明左子树的子树高度差大于1
        int left_high = solve(root.left);
        if(left_high == -1) return -1;
        //拿到右子树的高度值，如果为-1就证明右子树的子树高度差大于1
        int right_high = solve(root.right);
        if(right_high == -1) return -1;
        //如果说左右子树的高度差大于1，就返回-1
        if(Math.abs(left_high - right_high) > 1) return -1;
        //如果为平衡二叉树就去检验子树是否是平衡二叉树
        return Math.max(solve(root.left),solve(root.right)) + 1;
    }
}
